package 常见算法.分治之快速排序;

import java.util.Random;

/**
 * @Date 2024/6/21 22:10
 * @description: 数组中第K个最大元素 (建小根堆)
 * .            https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
 * @Author LittleNight
 */
public class likou215 {

    public int findKthLargest(int[] nums, int k) {
        // top K 问题， 可以用堆排序
        // 也可以用快速排序算法
        // 快速排序

        // 传入下标
        int key = qsort(nums, 0, nums.length - 1, k);
        return key;
    }

    /**
     * l， r 表示下标， 要排序的下标
     *
     * @param nums
     * @param l
     * @param r
     */
    private int qsort(int[] nums, int l, int r, int k) {
        // l >= r
        if(l == r) return nums[l];

        // 数组分三块, 不是从 0 开始， 因为要划分好多次
        // left 表示小于 key 的最右侧， right 表示大于 key 的最左侧
        int left = l - 1, right = r + 1, i = l;
        // 随机生成 key, 注意这个位置， nextInt(r - l + 1) + l 别忘了加 l
        int key = nums[new Random().nextInt(r - l + 1) + l];

        // 数组分三块， 核心代码。 都是不变的
        while(i < right) {
            if(nums[i] < key) swap(nums, i++, ++left);
            else if (nums[i] == key) i++;
            else swap(nums, i, --right);
        }
        // 分完之后， 判断在哪。然后就去哪里找
        // 和快排的主要区别就是在划分这里
        // [l, left] [left + 1, right - 1] [right, r]
        int b = (right - 1) - (left + 1) + 1, c = r - right + 1;
        if(c >= k)  return qsort(nums, right, r, k);
        else if (b + c >= k) return key;
        else return qsort(nums, l, left, k - b - c);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
